package com.origin.niuke.dynamic;

/**
 * 目标和
 * 算法：回溯、动态规划(背包问题)
 * 动态规划：
 * 数组和为 sum, 取负数的数字和为 negative, 则正数和为 sum - negative
 * sum - negative - negative = target
 * sum - target = 2 * negative
 * negative 表示背包容量, nums 表示物品
 *
 * @author yezh
 * @date 2023/1/9 21:35
 */
public class NC243 {

    int cnt = 0;

    public int findTargetSumWays_backtrack(int[] nums, int target) {
        // write code here
        if (nums.length == 0) return 0;
        dfs(0, nums, 0, target);
        return cnt;
    }

    void dfs(int idx, int[] nums, int cur, int target) {
        if (idx == nums.length) {
            if (cur == target) ++cnt;
            return;
        }
        dfs(idx + 1, nums, cur - nums[idx], target);
        dfs(idx + 1, nums, cur + nums[idx], target);
    }

    public int findTargetSumWays_dynamic(int[] nums, int target) {
        // write code here
        if (nums.length == 0) return 0;
        int sum = 0;
        for (int num : nums) sum += num;
        sum -= target;
        if (sum % 2 != 0) return 0;
        target = sum / 2;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int num : nums) for (int i = target; i >= num; i--) dp[i] += dp[i - num];
        return dp[target];
    }

}
